package study;

import java.util.*;

// 学习模仿
public class FindMinHeightTrees {

    public List<Integer> findMinHeightTrees(int num, int[][] edgeList) {
        List<Integer> ret = new ArrayList<>();
        if (num == 1) {
            ret.add(0);
            return ret;
        }
        List<Integer>[] adj = new List[num];
        for (int i = 0; i < num; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edgeList) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        int[] parent = new int[num];
        Arrays.fill(parent, -1);
        int first = bfs(0, parent, adj);
        int second = bfs(first, parent, adj);
        List<Integer> path = new ArrayList<>();
        parent[first] = Integer.MIN_VALUE;
        while (second != Integer.MIN_VALUE) {
            path.add(second);
            second = parent[second];
        }
        int m = path.size();
        if (m % 2 == 0) {
            ret.add(path.get(m / 2 - 1));
        }
        ret.add(path.get(m / 2));
        return ret;
    }

    public int bfs(int u, int[] parent, List<Integer>[] adj) {
        int n = adj.length;
        Queue<Integer> queue = new ArrayDeque<>();
        boolean[] visit = new boolean[n];
        queue.offer(u);
        visit[u] = true;
        int node = -1;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            node = curr;
            for (int v : adj[curr]) {
                if (!visit[v]) {
                    visit[v] = true;
                    parent[v] = curr;
                    queue.offer(v);
                }
            }
        }
        return node;
    }

    public static void main(String[] args) {
        FindMinHeightTrees minHeightTrees = new FindMinHeightTrees();
        int[][] input = {{1,0}, {1,2}, {1,3}};
        List<Integer> ret = minHeightTrees.findMinHeightTrees(4, input);
        System.out.println(Arrays.toString(ret.stream().toArray()));
    }
}
